#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 13:44
# @USER    : Shengji He
# @File    : SearchInsertPos.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        """
        Given a sorted array and a target value, return the index if the target is found. If not, return the index
        where it would be if it were inserted in order.

        You may assume no duplicates in the array.

        Example 1:
            Input: [1,3,5,6], 5

            Output: 2
        Example 2:
            Input: [1,3,5,6], 2

            Output: 1
        Example 3:
            Input: [1,3,5,6], 7

            Output: 4
        Example 4:
            Input: [1,3,5,6], 0

            Output: 0

        :param nums: List[int]
        :param target: int
        :return: int
        """
        # ans = 0
        # while nums:
        #     mid = len(nums) // 2
        #     if target == nums[mid]:
        #         return ans + mid
        #     elif target < nums[mid]:
        #         nums = nums[: mid]
        #         ans += 0
        #     else:
        #         nums = nums[mid + 1:]
        #         ans += mid + 1
        #
        # return ans
        nums.append(target)
        nums.sort()
        return nums.index(target)


if __name__ == '__main__':
    S = Solution()
    nums = [1, 2, 5, 6]
    target = 0
    # target = 7
    # target = 2
    # target = 5
    print(S.searchInsert(nums, target))
    print('done')
